1. Field of the Invention
The present invention relates to packet switching and routing systems, specifically to packet forwarding techniques.
2. Description of the Related Art
Routing lookup decisions are a well-known component of the modern routing and switching functions implemented in data communications networks. The routing lookups performed on Internet Protocol (IP) addresses and multi-protocol label switching (MPLS) labels often have varying latencies (or delays) associated in returning results. For example, most IP lookups require two accesses of the routing table to determine a destination address for the next hop. However, certain types of MPLS lookups, including virtual private network (VPN) lookups may require as many as seven accesses of the routing table.
Some modern routing/switching systems also employ a cache to speed the lookup function by storing certain addresses (such as, for example, frequently-encountered, high priority destinations or the like). When an IP destination address is presented for lookup, that address is first compared against the contents of the cache. If that IP address is found in the cache, the system bypasses the potentially lengthy lookup process. In systems employing the cache, packets (either plain IP packets or MPLS labeled packets) can transit the lookup sequence quickly. Thus, depending on the type of packet and whenever a cache hit occurs, packets arriving at the router may experience a variety of latencies in proceeding through the lookup process.
In today's environment of increasing network speeds, it is desirable to eliminate as many sources of routing delay as possible. The lookup throughput is different for different data traffic thus limiting attempts of eliminating latency in the lookup process. This is because the current router and switching systems do not distinguish between different incoming packet flows. At the end of a routing lookup, all packets are collected in a first-in-first-out (FIFO) buffer and are sent forward for further processing in the order that the packets were received.
The use of a single FIFO buffer can result in a head-of-line (HOL) blocking problem. The HOL blocking problem arises when several packets, for which the IP lookup has been completed, must wait behind a single packet at the head of the line whose lookup is still in process. For example, consider an MPLS packet arriving first, followed by several short IP packets, the destination addresses of which result in cache hits. The IP packets can bypass the lookup process by employing the cache. However, these IP packets must wait in the FIFO buffer until the lengthy lookup for the first MPLS packet at the head of the line is completed. Thus the head-of-line blocking problem can result in a loss of overall packet forwarding throughput in the router. What is needed is a system and method for improving packet-forwarding throughput by reducing or eliminating the head-of-line blocking problem.